package DoExercise.JianzhiOffer;

import java.util.Stack;

/**
 * 给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
 * {5,3,7,2,4,6,8},3
 * {4}
 * 按结点数值大小顺序第三小结点的值为4
 */
public class Offer062_二叉搜索树的第k大节点
{
    
    public static void main(String[] args)
    {
        Integer arr[] = new Integer[]{8, 6, 10, 5, 7, 9, 11};
        Offer000_Common.TreeNode node = Offer000_Common.deserializeTreeNode(arr);
        System.out.println(KthNode(node, 8).val);
    }
    
    /**
     * 二叉查找树的最左节点是其最小节点
     * 1、遍历至其最小节点
     * 2、按照左 根 右的顺序，遍历，遍历次数为 k 次
     *
     * @param pRoot
     * @param k
     * @return
     */
    public static Offer000_Common.TreeNode KthNode(Offer000_Common.TreeNode pRoot, int k)
    {
        if (pRoot == null || k < 0)
        {
            return null;
        }
        
        Stack<Offer000_Common.TreeNode> stack = new Stack();
        while (pRoot != null)
        {
            stack.push(pRoot);
            pRoot = pRoot.left;
        }
        
        Offer000_Common.TreeNode resNode = null;
        for (int i = 0; i < k; i++)
        {
            if (stack.isEmpty())
            {
                return null;
            }
            resNode = stack.peek();
            if (stack.peek().right == null)
            {
                stack.pop();
            } else if (stack.peek().right != null)
            {
                Offer000_Common.TreeNode pop = stack.pop().right;
                while (pop != null)
                {
                    stack.push(pop);
                    pop = pop.left;
                }
            }
        }
        return resNode;
    }
    
    int res, k;
    
    public int kthLargest(Offer000_Common.TreeNode root, int k)
    {
        this.k = k;
        dfs(root);
        return res;
    }
    
    public void dfs(Offer000_Common.TreeNode node)
    {
        if (node == null || this.k == 0) return;
        dfs(node.right);
        if (--this.k == 0)
        {
            res = node.val;
            return;
        }
        dfs(node.left);
    }
    
}
